import json
import time
import itertools
from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = [0] * n          # 保存当前正在构建的排列
        used = [False] * n      # 标记 nums 中的元素是否已被使用
        
        def dfs(i):
            if i == n:
                ans.append(path.copy())     
                return 
            for j in range(n):
                if not used[j]:
                    path[i] = nums[j]
                    used[j] = True
                    dfs(i+1)
                    used[j] = False
        
        dfs(0)
        return ans

class AlternativeSolution1:
    """使用内置库的解法，用于对比"""
    def permute(self, nums: List[int]) -> List[List[int]]:
        return [list(perm) for perm in itertools.permutations(nums)]

class AlternativeSolution2:
    """交换位置的回溯解法"""
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start == len(nums):
                result.append(nums[:])
                return
            
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]
        
        result = []
        backtrack(0)
        return result

def load_test_cases(filename="permutation_test_cases.json"):
    """加载测试用例"""
    try:
        with open(filename, 'r', encoding='utf-8') as f:
            data = json.load(f)
        return data["test_cases"], data.get("statistics", {})
    except FileNotFoundError:
        print(f"测试文件 {filename} 不存在，请先运行 gen.py")
        return [], {}

def compare_results(result1, result2):
    """比较两个排列结果是否相同"""
    if len(result1) != len(result2):
        return False
    
    # 将每个排列转换为元组并排序，以便比较
    set1 = set(tuple(perm) for perm in result1)
    set2 = set(tuple(perm) for perm in result2)
    
    return set1 == set2

def run_single_test(solution, test_case, test_id):
    """运行单个测试用例"""
    nums = test_case["input"]
    expected = test_case["expected"]
    description = test_case["description"]
    
    try:
        start_time = time.time()
        result = solution.permute(nums)
        end_time = time.time()
        
        # 检查结果正确性
        is_correct = compare_results(result, expected)
        
        return {
            "test_id": test_id,
            "description": description,
            "input": nums,
            "expected_count": len(expected),
            "actual_count": len(result),
            "is_correct": is_correct,
            "execution_time": end_time - start_time,
            "status": "PASS" if is_correct else "FAIL"
        }
    except Exception as e:
        return {
            "test_id": test_id,
            "description": description,
            "input": nums,
            "expected_count": len(expected),
            "actual_count": 0,
            "is_correct": False,
            "execution_time": 0,
            "status": "ERROR",
            "error": str(e)
        }

def run_comprehensive_test():
    """运行全面测试"""
    test_cases, stats = load_test_cases()
    if not test_cases:
        return
    
    solution = Solution()
    
    print("=== 全排列算法测试 ===")
    print(f"总测试用例数: {len(test_cases)}")
    print(f"总期望排列数: {stats.get('total_permutations', 'N/A')}")
    print()
    
    passed = 0
    failed = 0
    errors = 0
    total_time = 0
    
    print("测试结果详情:")
    print("-" * 80)
    
    for i, test_case in enumerate(test_cases):
        result = run_single_test(solution, test_case, i + 1)
        
        status_symbol = "✅" if result["status"] == "PASS" else "❌" if result["status"] == "FAIL" else "💥"
        
        print(f"{status_symbol} 测试 {result['test_id']:2d}: {result['description']}")
        print(f"   输入: {result['input']}")
        print(f"   期望排列数: {result['expected_count']}, 实际排列数: {result['actual_count']}")
        print(f"   执行时间: {result['execution_time']:.6f}秒")
        
        if result["status"] == "PASS":
            passed += 1
        elif result["status"] == "FAIL":
            failed += 1
        elif result["status"] == "ERROR":
            errors += 1
            print(f"   错误信息: {result.get('error', 'Unknown error')}")
        
        total_time += result["execution_time"]
        print()
    
    print("=" * 80)
    print("=== 测试汇总 ===")
    print(f"通过: {passed}")
    print(f"失败: {failed}")
    print(f"错误: {errors}")
    print(f"总计: {len(test_cases)}")
    print(f"成功率: {(passed / len(test_cases) * 100):.2f}%")
    print(f"总执行时间: {total_time:.6f}秒")

def compare_algorithms():
    """比较不同算法的性能"""
    test_cases, _ = load_test_cases()
    if not test_cases:
        return
    
    solutions = {
        "原始回溯算法": Solution(),
        "内置库算法": AlternativeSolution1(),
        "交换位置算法": AlternativeSolution2()
    }
    
    print("=== 算法性能比较 ===")
    
    # 选择一些具有代表性的测试用例
    representative_cases = []
    for case in test_cases:
        if len(case["input"]) <= 6:  # 避免运行时间过长
            representative_cases.append(case)
    
    print(f"比较测试用例数: {len(representative_cases)}")
    print()
    
    results = {name: {"total_time": 0, "success_count": 0} for name in solutions}
    
    for i, test_case in enumerate(representative_cases):
        nums = test_case["input"]
        expected = test_case["expected"]
        
        print(f"测试 {i+1}: {test_case['description']} - {nums}")
        print("-" * 40)
        
        for name, solution in solutions.items():
            try:
                start_time = time.time()
                result = solution.permute(nums)
                end_time = time.time()
                
                execution_time = end_time - start_time
                is_correct = compare_results(result, expected)
                
                results[name]["total_time"] += execution_time
                if is_correct:
                    results[name]["success_count"] += 1
                
                status = "✅" if is_correct else "❌"
                print(f"{name:15s}: {execution_time:.6f}秒 {status}")
                
            except Exception as e:
                print(f"{name:15s}: ERROR - {e}")
        
        print()
    
    print("=== 性能汇总 ===")
    for name, stats in results.items():
        avg_time = stats["total_"]
